#include <stack>
#include <deque>
#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> sliding_window(std::vector<int>&v,int k)
{
    // 进行预处理获取长度
    int n = v.size();
    std::vector<int>res;
    if (k > n)
    {
        return res;
    }

    // 使用deque容器解决这个问题
    std::deque<int>dq;

    // 遍历，并且只有当下边范围大于等于k时才进行push
    for (int i = 0;i < n;i++)
    {
        // Check whether empty and keep its order
        while (!dq.empty()&&v[dq.back()]<v[i])
        {
            dq.pop_back()   ;
        }
        dq.push_back(i);

        // According to the deque 
        // Pop front the excessive elements
        if (dq.front() <= i-k)
        {
            dq.pop_front();
        }

        // Check the i whether greater-equal than k-1
        if (i >= k-1)
        {
            res.push_back(v[dq.front()]);
        }
    }

    return res;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    
    std::vector<int>v = {2,3,1,6,4,3};
    std::vector<int>res = sliding_window(v,3)   ;

    for (int i :res)
    {
        std::cout<<i<<" ";
    }
    std::cout<<"\n";
    return 0;
}